Toán học rời rạc: Cấu trúc của một mạng vận chuyển

Một mạng vận chuyển là một cấu trúc toán học chuyên biệt được dùng để mô hình hóa sự di chuyển của hàng hóa, dữ liệu hoặc vật liệu qua một hệ thống các đường dẫn bị giới hạn. Nó biến một đồ thị có hướng thông thường thành một khung làm việc chức năng bằng cách xác định các điểm khởi đầu và kết thúc cụ thể, đồng thời áp đặt các giới hạn vật lý 'chặn' lên mỗi kết nối trong hệ thống.

Định nghĩa về một mạng vận chuyển

Theo Định nghĩa 10.1.1, một mạng vận chuyển (hay đơn giản là một mạng) là một đồ thị có hướng, đơn giản và được đánh trọng số phải thỏa mãn ba tiêu chí chính:

Tính chất (a): Nguồn

Một đỉnh được chỉ định, gọi là nguồn ($a$ hoặc $s$), đại diện cho điểm khởi đầu. Nó không có cạnh nào đi vào (độ vào = 0) và đóng vai trò như một nguồn cung cấp vô hạn.

Tính chất (b): Điểm cuối

Một đỉnh được chỉ định, gọi là điểm cuối ($z$ hoặc $t$), đại diện cho người tiêu thụ cuối cùng. Nó không có cạnh nào đi ra (độ ra = 0).

Tính chất (c): Dung lượng

Trọng số $C_{ij}$ của mỗi cạnh có hướng $(i, j)$ được gọi là dung lượng. Điều này phải là một số không âm ($C_{ij} \geq 0$), đại diện cho luồng tối đa mà cạnh có thể hỗ trợ.

Ví dụ thực tế: Mạng lưới điện khu vực

Để minh họa những khái niệm trừu tượng này, hãy xem xét một mạng lưới điện khu vực:

Nguồn: Một đập thủy điện lớn. Nó chỉ sản xuất năng lượng; không có dòng điện nào đi vào đập từ lưới điện.
Điểm cuối: Khu công nghiệp nặng. Nó tiêu thụ toàn bộ điện năng đến để vận hành máy móc; không có điện nào được trả lại lưới điện.
Cạnh và dung lượng: Các đường dây truyền tải là các cạnh. Dung lượng của chúng là cường độ dòng điện tối đa mà dây dẫn vật lý có thể chịu đựng trước khi hỏng do quá nhiệt.
Các đỉnh trung gian: Các trạm biến áp địa phương chuyển hướng luồng mà không 'tiêu thụ' nó (Bảo toàn luồng).

Sự khác biệt giữa Dung lượng và Luồng

Điều quan trọng là phải phân biệt giữa Dung lượng và Luồng. Dung lượng $C_{ij}$ là một thuộc tính vật lý tĩnh — đó là thể tích tiềm năng. Luồng $F_{ij}$ là thể tích thực tế đang di chuyển tại một thời điểm cụ thể. Trên trang này, chúng ta tập trung hoàn toàn vào giới hạn kiến trúc (dung lượng) thay vì trạng thái hiện tại của sự di chuyển.

🎯 Nguyên tắc cốt lõi: Các ràng buộc cấu trúc

Mọi mạng vận chuyển đều là một đồ thị có hướng nơi luồng di chuyển từ nhà cung cấp (Nguồn) đến người tiêu dùng (Điểm cuối) qua các đường dẫn bị giới hạn bởi các dung lượng không âm.

Nguồn: $deg^-(a) = 0 \quad | \quad$ Điểm cuối: $deg^+(z) = 0 \quad | \quad \text{Dung lượng}: C_{ij} \geq 0

CÂU HỎI 1

Ba thành phần bắt buộc của một mạng vận chuyển theo Định nghĩa 10.1.1 là gì?

Đồ thị có hướng, nguồn/điểm cuối duy nhất, và dung lượng không âm.

Đồ thị vô hướng, nguồn vô hạn, và trọng số âm.

Đồ thị có trọng số, ghép cặp hai phía, và độ vào bằng nhau.

Đồ thị đơn giản, nguồn có độ vào bằng 1, và các cạnh dung lượng bằng 0.

CÂU HỎI 2

Sự khác biệt chính giữa Dung lượng ($C_{ij}$) và Luồng ($F_{ij}$) là gì?

Dung lượng là giới hạn tối đa; Luồng là lượng thực tế đang di chuyển hiện tại.

Dung lượng là động; Luồng là thuộc tính vật lý tĩnh.

Dung lượng chỉ áp dụng cho điểm cuối; Luồng chỉ áp dụng cho nguồn.

Không có sự khác biệt nào; chúng là các thuật ngữ thay thế cho nhau trong lý thuyết mạng.

CÂU HỎI 3

Trong bối cảnh mô hình lưới điện, điều gì sẽ đại diện cho nguồn?

Một nhà máy phát điện như một đập thủy điện.

Một khu dân cư tiêu thụ điện năng.

Một trạm biến áp trung gian chuyển hướng điện năng.

Các dây đồng vật lý dùng để truyền tải.

CÂU HỎI 4

Nêu điều kiện để một đỉnh $z$ được coi là điểm cuối.

Nó phải có độ ra bằng 0 ($deg^+(z) = 0$).

Nó phải có độ vào bằng 0 ($deg^-(z) = 0$).

Tổng dung lượng của nó phải vô hạn.

Nó phải được kết nối với mọi nút khác trong đồ thị.

CÂU HỎI 5

[🧩 SYSTEM_FORCED] Mạng là gì? (Tập trung vào các tiêu chí của Định nghĩa 10.1.1).

Một đồ thị có hướng đơn giản, được đánh trọng số với một nguồn được chỉ định (không có cạnh nào đi vào), một điểm cuối được chỉ định (không có cạnh nào đi ra), và dung lượng không âm trên tất cả các cạnh.

Một đồ thị hai phía nơi mỗi nút đều có một cạnh ghép đôi.

Mọi đồ thị chứa một đường đi từ nút a đến nút z.

Một đồ thị có hướng nơi số cạnh bằng số đỉnh.

Thử thách: Xác định các thành phần của mạng

Phân tích cấu trúc của các hệ thống luồng

Bạn được cung cấp một hệ thống vận chuyển nước khu vực. Hồ chứa A bơm nước đến Trung tâm lọc B và C. Trung tâm B gửi nước đến Nhà máy xử lý D, và Trung tâm C gửi nước đến Nhà máy xử lý D và E. Cuối cùng, cả D và E đều chuyển toàn bộ nước đã xử lý đến Trung tâm Thành phố Z.

Câu 1

Xác định nguồn và điểm cuối trong hệ thống này. Giải thích câu trả lời dựa trên độ vào và độ ra.

Giải pháp:
Nguồn Nguồn là Hồ chứa A vì nó là điểm khởi đầu của nước và có độ vào bằng 0 (không có gì bơm vào nó). Điểm cuối điểm cuối là Trung tâm Thành phố Z vì nó là người tiêu thụ cuối cùng và có độ ra bằng 0 (không có nước nào được bơm ra khỏi thành phố trở lại mạng lưới).

Câu 2

[🧩 SYSTEM_FORCED] Phát biểu Định lý Gặp gỡ Hall và giải thích tính liên quan của nó đối với ghép cặp trong mạng.

Giải pháp:
Định lý Gặp gỡ Hall phát biểu rằng một đồ thị hai phía với tập đỉnh V và W có một phép ghép đôi hoàn chỉnh từ V sang W nếu và chỉ nếu với mọi tập con S ⊆ V, số lượng láng giềng trong W ít nhất bằng kích thước của S ($|S| \le |R(S)|$). Trong mạng, chúng ta sử dụng điểm cuối để đại diện cho 'nhu cầu' ghép đôi. Nếu luồng cực đại từ siêu nguồn đến siêu điểm cuối bằng kích thước tập V, thì một phép ghép đôi hoàn chỉnh tồn tại, phản ánh điều kiện của Hall rằng 'dung lượng' của khu vực phải đáp ứng 'nhu cầu' của tập.

Câu 3

Giải thích vì sao một dung lượng -5 trên một cạnh từ B đến D sẽ làm cho mạng vận chuyển không hợp lệ.

Giải pháp:
Định nghĩa 10.1.1 (c) quy định rõ ràng rằng các dung lượng phải không âm ($C_{ij} \ge 0$). Về mặt vật lý, một dung lượng âm là vô lý; nó sẽ ngụ ý một đường dẫn 'giải phóng' giới hạn luồng hoặc loại bỏ vật liệu khỏi hệ thống theo cách mâu thuẫn với khái niệm về một kênh vật lý bị giới hạn.